// 给定一个包含 n + 1 个整数的数组 nums，其数字都在 1 到 n 之间（包括 1 和 n），可知至少存在一个重复的整数。假设只有一个重复的整数，找出这个重复的数。

// 示例 1:

// 输入: [1,3,4,2,2]
// 输出: 2
// 示例 2:

// 输入: [3,1,3,4,2]
// 输出: 3
// 说明：

// 不能更改原数组（假设数组是只读的）。
// 只能使用额外的 O(1) 的空间。
// 时间复杂度小于 O(n2) 。
// 数组中只有一个重复的数字，但它可能不止重复出现一次。

#include <vector>

using std::vector;

// 二分法
class Solution {
public:
    int findDuplicate(vector<int>& nums) {
        int left = 1;
        int right = nums.size(); // n
        while (left < right) {
            int mid = left + (right - left) /2 ; // 防止数字过大超出整数范围
            int count = 0;
            for (int& num : nums) {
                if (num <= mid) ++count; // 统计小于中间值的数字个数
            }
            // 如果小于中间值的数字个数小于一半，就说明重复的数字在大于中间值的那一半
            if (count <= mid) left = mid + 1;
            else right = mid;
        }
        return right;
    }
};

// 快慢指针
// 抽象化成链表，思维很巧妙
// 根据题目nums[i]不会跳出1到n的范围
class Solution {
public:
    int findDuplicate(vector<int>& nums) {
        int slow = 0;
        int fast = 0;
        while (slow != fast || fast == 0) {
            slow = nums[slow];
            fast = nums[nums[fast]];
        }
        for (int i = 0; slow != i; i = nums[i]) {
            slow = nums[slow];
        }
        return slow;
    }
};

// Bit Manipulation 位操作
// 遍历每一位，然后对于 32 位中的每一个位 bit，
// 都遍历一遍从0到 n-1，将0到 n-1 中的每一个数都跟 bit 相 ‘与’，
// 若大于0，则计数器 cnt1 自增1。同时0到 n-1 也可以当作 nums 数组的下标，从
// 而让 nums 数组中的每个数字也跟 bit 相 ‘与’，
// 若大于0，则计数器 cnt2 自增1。
// 最后比较若 cnt2 大于 cnt1，则将 bit 加入结果 res 中。
// 因为对于每一位，0到 n-1 中所有数字中该位上的1的个数应该是固定的，
// 如果 nums 数组中所有数字中该位上1的个数多了，
// 说明重复数字在该位上一定是1
// 这样我们把重复数字的所有为1的位都累加起来，就可以还原出了这个重复数字
class Solution {
public:
    int findDuplicate(vector<int>& nums) {
        int res = 0;
        int n = nums.size();
        for (int i = 0; i < 32; ++i) {
            int bit = (1 << i);
            int cnt_1 = 0;
            int cnt_2 = 0;
            for (int j = 0; j < n; ++j) {
                if ((j & bit) > 0) ++cnt_1;
                if ((nums[j] & bit) > 0) ++cnt_2;
            }
            if (cnt_2 > cnt_1) res += bit;
        }
        return res;
    }
};

// O(n^2)，超时
class Solution {
public:
    int findDuplicate(vector<int>& nums) {
        int n = nums.size();
        for (int i = 0; i < n; ++i) {
            for (int j = i+1; j < n; ++j) {
                if (nums[i] == nums[j])
                    return nums[i];
            }
        }
        return 0;
    }
};